1. Field of the Invention
The present invention relates to a public key cryptosystem in which an encryption key is publicly disclosed while a decryption key is kept in secret, and more particularly, to a secret communication and authentication scheme based on a public key cryptosystem which can improve a decryption speed while maintaining an equivalent security level as the known public key cryptosystem such as RSA (Rivest-Shamir-Adleman) cryptosystem and Rabin cryptosystem and resolving problems associated with the known public key cryptosystem.
2. Description of the Background Art
In the field of communication, the cryptographic techniques are indispensable for protecting communication contents from a wiretapping or a forgery. In particular, the public key cryptosystem which only requires a simple key management is effective and has been widely used. The representative public key cryptosystems include the RSA cryptosystem which uses the modular exponent calculation and the Rabin cryptosystem which uses the encryption function in a form of a quadratic polynomial in modulo a product of two prime numbers, both of which are already in practical use.
Here, the RSA cryptosystem and the Rabin cryptosystem will be briefly described in this order. Note that, in the following description, (mod N) denotes a calculation in modulo N, .ident. denotes a congruence, LCM denotes the least common multiplier, GCD denotes the greatest common divisor, [A] denotes the Gaussian symbol for the largest integer not exceeding a number A, and (B) denotes a square root of a number B.
[Basic Principles of RSA Cryptosystem]
An encryption key of the RSA cryptosystem is given by a set (e, N) and a corresponding decryption key is given by a set (d, N), where e and N are public keys and d is a secret key. N is a product of two prime numbers (N=pq), and a set of prime numbers p and q for generating N is also referred to as a secret key.
Denoting a plaintext by M and a ciphertext by C, algorithms for the encryption E and the decryption D can be expressed by the following equations (1) and (2). EQU C=E(M)=M.sup.e (mod N) (1) EQU M=D(C)=C.sup.d (mod N) (2)
Here, it is assumed that M and C are integers in a range between 0 and N-1. If the original message is larger than N, the original message is to be divided into blocks of size N and the encryption and the decryption are to be applied block by block.
The encryption and the decryption are the one-to-one and onto mapping. Consequently, when M and C are represented by M for short, the following equation (3) holds. EQU D(E(M))=E(D(M))=M (3)
More specifically, the following equation (4) holds. EQU M.sup.ed.ident.M (mod N) (4)
The procedure for generating the cipher keys e, d and N such that the equation (4) holds for all M is as follows.
&lt;Key Generation in RSA Cryptosystem&gt;
First, arbitrary two large and mutually different prime numbers p and q are selected, and their product N=pq is calculated (first step).
Next, the least common multiplier L of (p-1) and (q-1) is calculated, and an arbitrary small integer e which is relatively prime with respect to L and smaller than L is selected (second step). That is: EQU L=LCM(p-1, q-1) (5) EQU GCD(e, L)=1, 1&lt;e&lt;L (6)
Next, using e and L obtained at the second step, the following congruence (7) is solved to obtain d (third step). EQU ed.ident.1 (mod L) (7)
In order to obtain d from the congruence (7), it is possible to use the Euclidean algorithm.
Note that this generation procedure selects e at the second step first and then calculate d at the third step, but it is also possible to select d first and then calculate e if desired.
&lt;Authentication Using RSA Cryptosystem&gt;
The authenticated communication using the RSA cryptosystem is carried out as follows.
First, a sender hashes an authentication message by using a hash function h so as to obtain an authenticator h(M).
Next, the authenticator h(M) is encrypted by using the sender's secret key d so as to obtain an encrypted authenticator S.
Next, a set of the encrypted authenticator S and the authentication message M are sent from the sender to a receiver. That is: EQU S.ident.(h(M).sup.d (mod N) (8)
When this set of the encrypted authenticator S and the authentication message M is received, the receiver decrypts the encrypted authenticator S by using the public key e of the sender, so as to obtain the authenticator h(M). That is: EQU h(M).ident.(S).sup.e (mod N) (9)
Next, the received authentication message M is hashed by using the hash function h so as to obtain an authenticator h(M).sup.o. Then, the decrypted authenticator h(M) and the authenticator h(M).sup.o obtained by hashing the authentication message M are compared to judge the authenticity. Namely, when they coincide the authentication message is judged as authentic and when they don't the authentication message is judged as not authentic.
In this manner, the RSA type public key cryptosystem device can also be used as an authenticated communication device by applying the public key calculation and the secret key calculation in reverse order.
Note that it is also possible to combine this authenticated communication with the secret communication so as to realize the authenticated secret communication in which a set of the encrypted authenticator S and the authentication message M is further encrypted by using the public key of the receiver.
[Basic Principles of Rabin Cryptosystem]
An encryption key of the Rabin cryptosystem is given by a set (b, N) and a decryption key is given by a set (b, p, q), where b and N are public keys and p and q are secret keys and N=pq.
Denoting a plaintext by M and a ciphertext by C, algorithm for the encryption E can be expressed by the following equation (10). EQU C=E(M)=M(M+b) (mod N) (10)
On the other hand, algorithm for the decryption D corresponds to the solving of the following equation (11) for M. EQU M.sup.2 +Mb-C.ident.0 (mod N) (11)
Here, N is a product of two large prime numbers p and q, that is: EQU N=pq (12)
so that the above equation (11) is equivalent to the following simultaneous congruences (13) and (14). EQU M.sup.2 +Mb-C.ident.0 (mod p) (13) EQU M.sup.2 +Mb-C.ident.0 (mod q) (14)
In other words, the decryption in the Rabin cryptosystem can be carried out only by an entity which knows the secret keys p and q. Also, the security of the Rabin cryptosystem relies on the difficulty in factoring N.
The decryption D amounts to obtaining M which simultaneously satisfies both congruences (13) and (14), and can be expressed by the following equations (15) and (16).
M=D(C)=-b/2.+-.((b/2).sup.2 +C) (mod p) (15) EQU M=D(C)=-b/2.+-.((b/2).sup.2 +C) (mod q) (16)
Here, b/2 (mod p) in the equation (15) represents an integer s which satisfies 2s.ident.b (mod p). Note that 2 and p are relatively prime so that it is always possible to obtain only one s.
Also, ((b/2).sup.2 +C) (mod p) in the equation (15) represents a non-negative integer t which satisfies t.sup.2.ident.(b/2).sup.2 +C (mod p). Assuming that t exists and p is a prime number in a form of 4.alpha.+3 (.alpha.: integer), (b/2).sup.2 +C becomes the quadratic residue in mod p so that t can be easily obtained by the following equation (17). EQU t=((b/2).sup.2 +C).sup..alpha.+1 (mod p) (17)
The equation (16) can also be solved similarly as the equation (15).
The encryption function E of the Rabin cryptosystem is defined for all integers in a range of [0, N-1] as should be apparent from the above equation (10), so that every plaintext can be encrypted. Also, the encryption function E is a single-valued function, so that a ciphertext C.0. corresponding to a plaintext M.0. can be determined uniquely. However, the decryption function D is a multi-valued function, so that M.0. is not necessarily determined uniquely even when C.0. corresponding to M.0. is decrypted.
To cope with this problem, a meaningful attribute information (such as a sender ID, a receiver ID, a date, etc.) is included in the original plaintext M.0.. Then, the receiver determines the true plaintext as a message containing this attribute information among decrypted messages M.sub.i (1.ltoreq.i.ltoreq.4).
&lt;Key Generation in Rabin Cryptosystem&gt;
The key generation in the Rabin cryptosystem is similar to the first step alone of the key generation in the RSA cryptosystem described above in that arbitrary two large and mutually different prime numbers p and q are selected, and their product N=pq is calculated. In addition, b which satisfies 0.ltoreq.b.ltoreq.N is determined. Then, p and q are set as the secret keys while N and b are set as the public keys.
&lt;Authentication Using Rabin Cryptosystem&gt;
The decryption function D of the Rabin cryptosystem is defined for a part of integers in a range of [0, N-1]. That is, in the Rabin cryptosystem, it is not necessarily possible to realize the authenticated communication for an arbitrary plaintext M (0.ltoreq.M.ltoreq.N-1). Here, a condition required for realizing the authenticated communication is that the calculations of the equations (15) and (16) can be defined, or more specifically, that (b/2).sup.2 +M becomes the quadratic residue in mod p and mod q.
In terms of the quadratic residue symbols (also called Legendre symbols), this condition can be expressed as that the following congruences (18) and (19) hold. ##EQU1##
When a digital signature transformation D is applied to a certain plaintext M.0. for which the authenticated communication is possible, each one of four signed messages S.sub.1, S.sub.2, S.sub.3 and S.sub.4 is obtained at nearly equal probability of 1/4. The plaintext M.0. can be recovered by applying the recovery processing to any of these four signed messages, so that it suffices to carry out a communication using any one signed message alone.
Next, a measure to be taken in order to make it possible to attach a digital signature to an arbitrary plaintext M (0.ltoreq.M.ltoreq.N-1) will be described.
To this end, it is necessary to apply a certain type of transformation f.sub.j to the plaintext M first. That is: EQU M.sub.j =f.sub.j (M), j=0, 1, 2 . . . (20)
where f.0. represents a case of no transformation. As a concrete example of f.sub.j, it is possible to use a function defined by the following equation (21) for example. EQU f.sub.j (M)=M+j (21)
Then, the necessary measure can be taken by the following procedure.
First, the sender checks whether M.sub.j satisfies the congruences (18) and (19) or not by setting j=0. If not, the checking of whether M.sub.j satisfies the same condition or not is repeated by sequentially updating j to j+1. By the repeated trials, the transformation that satisfies the condition can be found by checking four times in average, as can be seen from the following equation (22). ##EQU2##
The obtained transformation is denoted as f.sub.j * and the plaintext after the transformation is denoted as M.sub.j *.
Next, the sender sends a signed message S (=D(M.sub.j *)) to the receiver by attaching f.sub.j * thereto. The receiver recovers M.sub.j * from S by using the public key, and also obtains M by further applying an inverse function f.sub.j *.sup.-1 of f.sub.j * to M.sub.j *. If M is a meaningful information, the authenticity of the sender can be verified.
Note that it is also possible to realize the authenticated communication using the Rabin type cryptosystem similarly as in a case of the RSA type cryptosystem described above, by sending a set of the authentication message M and the encrypted authenticator S obtained by hashing the authentication message M and encrypting the hashed authenticator h(M) by using the sender's secret key from the sender to the receiver, and judging the authenticity at the receiver side by comparing the decrypted authenticator h(M) and the authenticator h(M).sup.o obtained by hashing the authentication message M.
In this manner, the Rabin type public key cryptosystem device can also be used as an authenticated communication device by applying the public key calculation and the secret key calculation in reverse order.
Now, in general, the performance of the cryptographic technique is evaluated in terms of the security level against an attack that attempts to break the cryptosystem, and the speed of encryption/decryption. The cryptosystem with a high security level and a fast encryption/decryption speed can be considered as an excellent cryptosystem.
The security of the public key cryptosystem such as the RSA cryptosystem and the Rabin cryptosystem is based on the fact that it is difficult to obtain the secret key that functions as the decryption key from the public key that functions as the encryption key because of an enormous amount of calculations required.
For the RSA cryptosystem, it has been shown that the plaintext can be obtained from the ciphertext if the public key can be factorized (see, [1] R. L, Rivest, A. Shamir and L. Adleman: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Comm. ACM, Vol. 21, No. 2, pp. 120-126 (1978)).
Thus the security of the public key cryptosystem such as the RSA cryptosystem relies on the computational difficulty in obtaining the secret key from the public key. By increasing a size of the public key, the security level can also be increased accordingly.
On the other hand, the RSA cryptosystem requires the higher degree modular exponent calculations, so that a major drawback of the RSA cryptosystem has been the fact that an amount of required calculations is large and the encryption/decryption is time consuming.
In this regard, the encryption/decryption can be made faster by reducing an amount of the modular exponent calculations, but this can only be done by reducing a size of the public key and this in turn leads to a lowering of the security level of the cryptosystem.
For example, when the exponent factor of the cryptosystem given by the public key e is small, it has been shown that the RSA cryptosystem can be easily cryptanalyzed (see, [2] J. Hastad: "Solving simultaneous Modular Equations", SIAM Journal of Computing, Vol. 17, No. 2, pp. 336-341 (1988); [3] D. Coppersmith, M. Franklin, J. Patarin and M. Reiter: "Low-Exponent RSA with Related Messages", Advances in Cryptology--EUROCRYPT '96 Proceedings, LNCS 1070, pp. 1-9 (1996); [4] D. Coppersmith, "Finding a Small Root of a Univariate Modular Equation" Advances in Cryptology--EUROCRYPT '96 Proceedings, LNCS 1070, pp. 155-165 (1996)). In practice, this situation corresponds to a case of sending the same plaintext to plural correspondents (a case of multicast communication), a case of having a polynomial relationship between two plaintexts, a case of using a small number of bits in the plaintext, etc.
For the Rabin cryptosystem, the fact that obtaining the original plaintext from the ciphertext alone is computationally equivalent to being able to factorize the public key has been shown (see, [5] M. O. Rabin: "Digitalized Signatures and Public-Key Functions as Intractable as Factorization", MIT Technical Report MIT/LCS/TR-212 (1979)).
Also, the cryptosystem extending the Rabin cryptosystem into two dimensions has been proposed (see, [6] K. Koyama: "Security and Unique Decipherability of Two-Dimensional Public Key Cryptosystems". IEICE Transactions, Vol. E73, No. 7, pp. 1058-1067 (1990)).
The characteristic of the Rabin cryptosystem is that the encryption is fast. However, in the known public key cryptosystem including the Rabin cryptosystem, in a case of carrying out a secret communication of the plaintext with a data length exceeding that of the public key, it has been necessary to divide the plaintext into blocks in the size of the public key (or twice the size of the public key in two dimensional case) and encrypt each block separately. In other words, a length of the public key dictated a unit of secret communication.
Also, the Rabin cryptosystem has been associated with a drawback that it is very weak against the partial cryptanalysis. For example, it has also shown that the Rabin cryptosystem can be easily cryptanalyzed in a case of multicast communication, a case of having a polynomial relationship between two plaintexts, a case of using a small number of bits in the plaintext, etc. (see references [2], [3] and [4] quoted above).
Thus the known cryptosystems have been associated with a problem that the security and the speed are not compatible with each other because a higher security level requires a larger key size but a larger key size implies a lower encryption/decryption speed.